package com.xinheyun.demo.leetcode;

import java.util.Arrays;
import org.junit.Test;

/**
 * @description: TODO
 * @author: Sarah
 * @modified By: Sarah
 * @date: Created in 2021/8/31 15:00
 * @version:v1.0
 */
public class test1049 {

    @Test
    public void test() {
        int[] stones = {53,54,3,61,67};
        int sum = Arrays.stream(stones).sum();
        int[] dp = new int[sum + 1];
        dp[0] = 1;
        for (int num : stones) {
            for (int i = sum; i >=num; i--) {
                dp[i]+= dp[i - num];
                if(dp[i]!=0&&dp[i]>sum/2+1){
                    continue;
                }
            }
        }
        int ans = 0;
        int i = 0;
        if (sum % 2 != 0) {
            i = sum / 2 + 1;
        } else {
            i = sum / 2;
        }
        for (; i <= sum; i++) {
            if (dp[i] != 0) {
                ans = 2 * i - sum;
                break;
            }
        }
        System.out.println(ans+" "+sum+" "+i);
    }
}
